package edu.cmu.cs771.hw1;

/**
 * This class implements a doubly linked list of characters in Java. 
 * The instance variables head and tail are initially null. 
 * As elements are added head points to the first element on the list and tail points to the last element. Each node on the list is of type DoubleNode. 
 * Each DoubleNode holds a pointer to the previous node and a pointer to the next node in the list. 
 * @author songluo
 *
 */
public class DoublyLinkedList {
	private DoubleNode head;
	private DoubleNode tail;
	
	/**
	 * Constructs a new DoublyLinkedList object with head and tail as null.
	 */
	public DoublyLinkedList() {
		head = null;
		tail = null;
	}
	
	/**
	 * Returns true if the list is empty false otherwise 
	 * @return true if the list empty false otherwise
	 */
	public boolean isEmpty(){
		return head == null;
	}
	
	/**
	 * Add a character node containing the character c to the end of the linked list. This routine does not require a search.
	 * @param c a single character
	 */
	public void addCharAtEnd(char c){
		DoubleNode n = new DoubleNode(tail, c, null);
		if(isEmpty()){
			head = tail = n;
		}else{
			tail.setNext(n);
			tail = n;
		}
	}

	/**
	 * Add a character node containing the character c to the front of the linked list. No search is required. 
	 * @param c a single character
	 */
	public void addCharAtFront(char c){
		DoubleNode n = new DoubleNode(null, c, head);
		if(isEmpty()){
			head = tail = n;	
		}else{
			head.setPrev(n);
			head = n;
		}
	}
	
	/**
	 * Remove and return the character at the front of the doubly linked list. 
	 * @return the character at the front precondition: the list is not empty
	 */
	public char removeCharFromFront(){
		char ch = head.getC();
		if(!isEmpty()){		
			if(head == tail){
				head = tail = null;
			}else{
				head = head.getNext();
				head.setPrev(null);
			}
		}
		return ch;
	}
	
	/**
	 * Remove and return the character at the end of the doubly linked list. No searching is required. 
	 * @return the character at the end precondition: the list is not empty
	 */
	public char removeCharAtEnd(){
		char ch = tail.getC();
		
		if(!isEmpty()){
			if(head == tail){
				head = tail = null;
			}else{
				tail = tail.getPrev();
				tail.setNext(null);
			}
		}
		
		return ch;
	}
	
	/**
	 * Counts the number of nodes in the list. We are not maintaining a counter so a search is required. 
	 * @return the number of nodes in the doubly linked list between head and tail inclusive
	 */
	public int countNodes(){
		DoubleNode cn = head;
		int count = 0;
		while(cn != null){
			count++;
			cn = cn.getNext();
		}
		return count;
	}
	
	/**
	 * Deletes the first occurence of the character c from the list. If the character c is not in the list then no modifications are made. This method needs to search the list. 
	 * @param c the character to be searched for. 
	 * @return true if a deletion occurred and false otherwise
	 */
	public boolean deleteChar(char c){
		DoubleNode cn = head;
		while(cn.getC() != c){
			cn = cn.getNext();
		}
		
		if(cn != null){
			if(cn.getPrev() == null){
				head = cn.getNext();
				if(!isEmpty()){
					head.setPrev(null);
				}
			}else if(cn.getNext() == null){
				tail = cn.getPrev();
				if(!isEmpty()){
					tail.setNext(null);
				}
			}else{
				cn.getPrev().setNext(cn.getNext());
				cn.getNext().setPrev(cn.getPrev());
			}
		}
		
		return cn != null;
	}
	
	/** 
	 * Returns the list as a String. The class DoubleNode has a toString that will be called from this toString. The String returned must be presented clearly. Null pointers must be represented differently than non-null pointers. 
	 * @see java.lang.Object#toString()
	 * @return a String containing the characters in the list
	 */
	public String toString(){
		DoubleNode cn = head;
		String str = "";
		while(cn != null){
			str += cn.getC();
			//System.out.print(cn.getC());
			cn = cn.getNext();
		}
		
		return str;
	}
	
	/**
	 *Reverse the list. a -> b -> c becomes c -> b -> a  
	 */
	public void reverse(){
		DoubleNode cn = head;
		DoubleNode tmp = null;
		while(cn != null){
			tmp = cn.getNext();
			cn.setNext(cn.getPrev());
			cn.setPrev(tmp);
			
			cn = cn.getPrev();
		}
		tmp = head;
		head = tail;
		tail = tmp;
		head.setPrev(null);
		tail.setNext(null);
	}
	
	/**
	 * Test driver for DoublyLinkedList 
	 */
	public static void main(String a[]) {
		
		DoublyLinkedList list = new DoublyLinkedList();
		list.addCharAtEnd('H');
		list.addCharAtEnd('e');
		list.addCharAtEnd('l');
		list.addCharAtEnd('l');
		list.addCharAtEnd('o');
		System.out.println(list);
		System.out.println("Deleting l");
		list.deleteChar('l');
		System.out.println(list);
		System.out.println("Deleting H");
		list.deleteChar('H');
		System.out.println(list);
		System.out.println("Deleting o");
		list.deleteChar('o');
		System.out.println(list);
		System.out.println("Deleting e");
		list.deleteChar('e');
		System.out.println(list);
		System.out.println("Deleting l");
		list.deleteChar('l');
		System.out.println(list);
		list.addCharAtFront('o');
		list.addCharAtFront('l');
		list.addCharAtFront('l');
		list.addCharAtFront('e');
		list.addCharAtFront('H');
		System.out.println(list);
		
		System.out.println(list.countNodes());
		
		System.out.println("Popping everything");
		while(!list.isEmpty()){
			System.out.println(list.removeCharFromFront());
		}
		
		list.addCharAtFront('o');
		list.addCharAtFront('l');
		list.addCharAtFront('l');
		list.addCharAtFront('e');
		list.addCharAtFront('H');
		
		System.out.println("Popping everything from the end");
		while(!list.isEmpty()){
			System.out.println(list.removeCharAtEnd());
		}
		System.out.println(list.countNodes());
		
		list.addCharAtEnd('o');
		list.addCharAtEnd('l');
		list.addCharAtEnd('l');
		list.addCharAtEnd('e');
		list.addCharAtEnd('H');
	
		list.reverse();
		System.out.println(list);
		
		list.reverse();
		System.out.println(list);
		
	}

}
